Magellan sinh vào khoảng năm 1480 tại Sabrosa, gần Vila Real, tỉnh Trás-os-Montes, Bồ Đào Nha. Cha ông là Rui de Magalhães (ông nội là Pedro Afonso de Magalhães và bà nội Quinta de Sousa) và mẹ Alda de Mesquita, gia đình ông có các anh em Duarte de Sousa, Diogo de Sousa và Isabel de Magalhães. Sau khi ba mẹ mất vào năm ông lên mười, ông trở thành cậu bé giúp việc cho Hoàng hậu Leonor trong triều đình Hoàng gia Bồ Đào Nha theo truyền thống của gia đình.

Vào tháng 3, 1505, ở tuổi 25, Magellan gia nhập hạm đội gồm 22 tàu, đứng đầu là Francisco de Almeida Phó Vương đầu tiên của Ấn Độ thuộc Bồ Đào Nha. Mặc dù tên của ông không được tìm thấy trong biên niên sử các cuộc chiến tranh ở Ấn Độ, những điều còn lại người ta biết về ông là ông đã trải qua tám năm ở Goa, Cochin và Quilon. Ông đã tham dự một vài trận đánh, bao gồm trận Cannanore năm 1506, nơi ông đã bị thương. Năm 1509, ông dự trận đánh Diu[4] và sau đó đi cùng thủy thủ đoàn của Diogo Lopes de Sequeira với tư cách Sứ thần đầu tiên của Bồ Đào Nha đến Malacca. Trong thủy thủ đoàn còn có bạn ông và có thể là người anh em họ Francisco Serrão.[5] Tháng 9, sau khi đến Malacca, chuyến đi trở thành thảm họa khi họ rơi vào một âm mưu tấn công và phải rút lui. Trong dịp này Magellan đóng một vai trò then chốt giúp cho đoàn hải hành không bị tiêu diệt hoàn toàn, ông đã cảnh báo Sequeira và chiến đấu dũng cảm cứu Francisco Serrão, người vốn đã lên bờ trước cuộc tấn công.[6] Sau đó, ông được chú ý tới và thăng chức.

Năm 1511, dưới quyền của vị Thống sứ mới là Afonso de Albuquerque, Magellan và Serrão tham gia vào cuộc chinh phục bán đảo Malacca, đồng thời phục hận cho thất bại của Sequeira. Sau cuộc chiến họ chia tay: Magellan được thăng cấp, kèm một số tiền lớn. Cùng với một thổ dân Malay ông đã nhận và rửa tội với cái tên Enrique của Malacca, ông trở về Bồ Đào Nha trong năm 1512. Serrão khởi hành trong chuyến thám hiểm đầu tiên đi tìm "Quần đảo Spice "trong vùng Moluccas, và sau đó ở lại luôn tại vùng đất đó. Serrão kết hôn với một người phụ nữ vùng Amboina và trở thành một cố vấn quân sự cho Sultan của vùng Ternate, Bayan Sirrullah. Serrão đã viết nhiều thư cho Magellan và cung cấp thông tin về các vùng đất xa xôi trồng cây gia vị, khiến ông quyết định đi thám hiểm chúng.[7][8]